/**
 * @file   Quick.cpp
 * @author xingyifan
 * @date   2021/08/22 14:50:17
 * 
 * @brief  quick sort
 * 
 * 
 */

#include "Quick.h"

//分割[a,b)
int partition(double A[], int a, int b)
{
    int right = b;
    int left = a;

    while (right > left)
    {
        right--;
        while (A[right] >= A[a] && right > left)
        {
            right--;
        }
        while (A[left] < A[a] && right > left)
        {
            left++;
        }
        double tmp = A[right];
        A[right] = A[left];
        A[left] = tmp;
    }

    double tmp = A[left];
    A[left] = A[a];
    A[a] = tmp;

    return left;
}

void Quick_Sort(double A[], int a, int b)
{
    if (b > a + 1)
    {
        int mid = partition(A, a, b);
        Quick_Sort(A, a, mid);
        Quick_Sort(A, mid + 1, b);
    }
}

void Quick_Sort(int n, double A[])
{
    Quick_Sort(A, 0, n);
    for (int i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
}